      1  import java.util.NoSuchElementException;

      2

      3  /**

      4     A linked list is a sequence of nodes with efficient

      5     element insertion and removal. This class

      6     contains a subset of the methods of the standard

      7     java.util.LinkedList class.

      8  */

      9  public class LinkedList

     10  {

     11     private Node first;

     12

     13     /**

     14        Constructs an empty linked list.

     15     */

     16     public LinkedList()

     17     {

     18        first = null;

     19     }

     20

     21     /**

     22        Returns the first element in the linked list.

     23        @return the first element in the linked list

     24     */

     25     public Object getFirst()

     26     {

     27        if (first == null) { throw new NoSuchElementException(); }

     28        return first.data;

     29     }

     30

     31     /**

     32        Removes the first element in the linked list.

     33        @return the removed element

     34     */

     35     public Object removeFirst()

     36     {

     37        if (first == null) { throw new NoSuchElementException(); }

     38        Object element = first.data;

     39        first = first.next;

     40        return element;

     41     }

     42

     43     /**

     44        Adds an element to the front of the linked list.

     45        @param element the element to add

     46     */

     47     public void addFirst(Object element)

     48     {

     49        Node newNode = new Node();

     50        newNode.data = element;

     51        newNode.next = first;

     52        first = newNode;

     53     }

     54

     55     /**

     56        Returns an iterator for iterating through this list.

     57        @return an iterator for iterating through this list

     58     */

     59     public ListIterator listIterator()

     60     {

     61        return new LinkedListIterator();

     62     }

     63

     64     class Node

     65     {

     66        public Object data;

     67        public Node next;

     68     }

     69

     70     class LinkedListIterator implements ListIterator

     71     {

     72        private Node position;

     73        private Node previous;

     74        private boolean isAfterNext;

     75

     76        /**

     77           Constructs an iterator that points to the front

     78           of the linked list.

     79        */

     80        public LinkedListIterator()

     81        {

     82           position = null;

     83           previous = null;

     84           isAfterNext = false;

     85        }

     86

     87        /**

     88           Moves the iterator past the next element.

     89           @return the traversed element

     90        */

     91        public Object next()

     92        {

     93           if (!hasNext()) { throw new NoSuchElementException(); }

     94           previous = position; // Remember for remove

     95           isAfterNext = true;

     96

     97           if (position == null)

     98           {

     99              position = first;

    100           }

    101           else

    102           {

    103              position = position.next;

    104           }

    105

    106           return position.data;

    107        }

    108

    109        /**

    110           Tests if there is an element after the iterator position.

    111           @return true if there is an element after the iterator position

    112        */

    113        public boolean hasNext()

    114        {

    115           if (position == null)

    116           {

    117              return first != null;

    118           }

    119           else

    120           {

    121              return position.next != null;

    122           }

    123        }

    124

    125        /**

    126           Adds an element before the iterator position

    127           and moves the iterator past the inserted element.

    128           @param element the element to add

    129        */

    130        public void add(Object element)

    131        {

    132           if (position == null)

    133           {

    134              addFirst(element);

    135              position = first;

    136           }

    137           else

    138           {

    139              Node newNode = new Node();

    140              newNode.data = element;

    141              newNode.next = position.next;

    142              position.next = newNode;

    143              position = newNode;

    144           }

    145

    146           isAfterNext = false;

    147        }

    148

    149        /**

    150           Removes the last traversed element. This method may

    151           only be called after a call to the next() method.

    152        */

    153        public void remove()

    154        {

    155           if (!isAfterNext) { throw new IllegalStateException(); }

    156

    157           if (position == first)

    158           {

    159              removeFirst();

    160           }

    161           else

    162           {

    163              previous.next = position.next;

    164           }

    165           position = previous;

    166           isAfterNext = false;

    167        }

    168

    169        /**

    170           Sets the last traversed element to a different value.

    171           @param element the element to set

    172        */

    173        public void set(Object element)

    174        {

    175           if (!isAfterNext) { throw new IllegalStateException(); }

    176           position.data = element;

    177        }

    178     }

    179  }